class code4 {
    //找到第一个count大于i的即是重复元素
    public int findDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        while(left<right) {
            int mid = ((right-left)>>1) +left;

            //统计<=mid的元素的个数
            int count = 0;
            for(int x:nums) {
                if(x <= mid) {
                    count++;
                }
            }

            //count > mid =》重复数一定在左边
            if(count > mid) {
                right = mid;
            } else {
                left = mid+1;
            }
        }
        return left;
    }
}